import java.util.Comparator;

public class BubbleSort<T> {

    private Comparator<T> comparator;

    public BubbleSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void imp1(T[] array) {
        int length = array.length;

        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (comparator.compare(array[j], array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                }
            }
        }
    }

    public void imp2(T[] array) {
        int length = array.length;

        for (int i = 0; i < length - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < length - 1 - i; j++) {
                if (comparator.compare(array[j], array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }

        }
    }

    public void imp3(T[] array) {
        int length = array.length;
        int lastJ = length - 1;
        int lastSwap = -1;

        for (int i = 0; i < length - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < lastJ; j++) {
                if (comparator.compare(array[j], array[j + 1]) > 0) {
                    swap(array, j, j + 1);
                    swapped = true;
                    lastSwap = j;
                }
            }

            if (!swapped) {
                break;
            }

            lastJ = lastSwap;
        }
    }
}
